package com.二叉搜索树.练习题;

import java.util.LinkedList;

public class Leetcode98 {
    /**
     *验证二叉搜索树
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     *
     * 有效 二叉搜索树定义如下：
     *
     * 节点的左子树只包含 严格小于 当前节点的数。
     * 节点的右子树只包含 严格大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     *
     * 输入：root = [2,1,3]
     * 输出：true
     */
    public boolean isValidBST(TreeNode root) {
        TreeNode p = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        long prev = Long.MIN_VALUE;
        while(p != null || !stack.isEmpty()){
            if(p != null){
                stack.add(p);
                p = p.left;
            }else {
                TreeNode pop = stack.pop();
                if(pop.val <= prev){
                    return false;
                }
                prev = pop.val;
                p = pop.right;
            }
        }
        return true;
    }
}
